package com.wangwr.algorithm;

import com.sun.javafx.scene.control.ReadOnlyUnbackedObservableList;
import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

import java.util.*;

@SpringBootApplication
public class AlgorithmApplication {

    public static void main(String[] args) {
        SpringApplication.run(AlgorithmApplication.class, args);
//        int []p=new int[3];
//        int[] p = {282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923};
//        String[] p = {"Hello", "Alaska", "Dad", "Peace"};
//        int[] p1 = {823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612};
        int[] p1 = {1, 3, 1, 5, 4};
////        p={1,2};
//        Integer[] arr = {1, 2, 3};
//        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(arr));
//        Set<String> a = new HashSet<>();
//        Set<String> b = new HashSet<>();
//        a.add("ab");
//        a.add("ac");
//        a.add("ad");
//        b.add("ba");
//        b.add("bb");
//        b.add("bc");
//        a.retainAll(b);
//        System.out.println(a);

        int res = findPairs(p1, 0);
        System.out.println(res);
    }


    /**
     * 37. 解数独
     * @param board
     */
    public void solveSudoku(char[][] board) {
        //判断合法性
        if(board==null||board.length!=9||board[0]==null||board[0].length!=9)
            return;
        backTrace(board,0,0);
    }

    /**
     * 回溯
     * @param board
     * @param row
     * @param col
     * @return
     */
    public boolean backTrace(char [][]board,int row,int col){
        int n=board.length;
        //进到下一行回溯
        if(col==9)
            return backTrace(board,row+1,0);
        //全部回溯完毕
        if(row==n)
            return true;
        //已给数字，跳过
        if(board[row][col]!='.')
            return backTrace(board,row,col+1);
        //尝试赋值
        for (char c='1';c<='9';c++){
            //判断数字合法性
            if(!isValid(board,row,col,c))
                continue;
            //合法赋值
            board[row][col]=c;
            //下一列回溯赋值
            if(backTrace(board,row,col+1))
                return true;
            //赋值错误，回溯初始值
            board[row][col]='.';
        }
        return false;
    }

    /**
     * 判断填入数字是否合法
     * @param board
     * @param row
     * @param col
     * @param c
     * @return
     */
    public boolean isValid(char[][]board,int row,int col,char c){
        for (int i=0;i<9;i++){
            if(board[row][i]==c)return false;//行判断
            if(board[i][col]==c)return false;//列判断
            if(board[(row/3)*3+i/3][(col/3)*3+i%3]==c)return false;//九宫格判断
        }
        return true;
    }

    /**
     * 532. 数组中的K-diff数对
     * @param nums
     * @param k
     * @return
     */
    public static int findPairs(int[] nums, int k) {
        int result = 0;
        Arrays.sort(nums);
        if (nums.length <= 1) return result;
        if (nums[0] == nums[nums.length - 1])
            return 1;

        int temp=Integer.MIN_VALUE;
        int index=1;
        for (int i=0;i<nums.length;i++){
            if(nums[i]+k>nums[nums.length-1])
                break;
            if(nums[i]==temp)
                continue;
            if(index<=i){
                index=i+1;
            }
            for (int j=index;j<nums.length;j++){
                if(nums[i]+k==nums[j]){
                    result++;
                    index=j;
                    break;
                }
            }
            temp=nums[i];
        }
        return result;
    }

    /**
     * 521. 最长特殊序列 Ⅰ
     *
     * @param a
     * @param b
     * @return
     */
    public static int findLUSlength(String a, String b) {
        if (a.length() != b.length()) {
            return Math.max(a.length(), b.length());
        }
        int result = -1;
        if (a.equals(b))
            return result;
        if (a.length() == b.length() && !a.equals(b))
            return a.length();
        return result;
    }

    /**
     * 520. 检测大写字母
     *
     * @param word
     * @return
     */
    public static boolean detectCapitalUse(String word) {
        if (word.equals(word.toUpperCase()))
            return true;
        if (word.equals(word.toLowerCase()))
            return true;
        int count = 0, index = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) - 'A' <= 25) {
                index = i;
            }
        }
        if (index == 0)
            return true;
        return false;
    }

    /**
     * 509. 斐波那契数(递归法)
     *
     * @param N
     * @return
     */
    public static int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return fib(N - 1) + fib(N - 2);
    }

    /**
     * 迭代法
     *
     * @param N
     * @return
     */
    public int fib2(int N) {
        if (N <= 1) {
            return N;
        }
        int prant = 0, result = 0, next = 1;
        for (int i = 2; i <= N; i++) {
            result = prant + next;
            prant = next;
            next = result;
        }
        return result;
    }

    /**
     * 507. 完美数
     *
     * @param num
     * @return
     */
    public static boolean checkPerfectNumber(int num) {
        if (num == 1) return false;
        boolean flag = false;
        ArrayList<Integer> set = new ArrayList<>();
        set.add(1);
        int temp = num;
        for (int i = 2; i < temp; i++) {
            if (num % i == 0) {
                set.add(i);
                set.add(num / i);
                temp = num / i;
            }
        }
        int result = 0;
        for (int i = 0; i < set.size(); i++) {
            result += set.get(i);
        }
        if (result == num)
            flag = true;
        return flag;
    }

    /**
     * 506. 相对名次
     *
     * @param nums
     * @return
     */
    public static String[] findRelativeRanks(int[] nums) {
        String[] result = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int rank = getNumRank(nums, nums[i]);
            switch (rank) {
                case 1:
                    result[i] = "Gold Medal";
                    break;
                case 2:
                    result[i] = "Silver Medal";
                    break;
                case 3:
                    result[i] = "Bronze Medal";
                    break;
                default:
                    result[i] = String.valueOf(rank);
                    break;
            }
        }
        return result;
    }

    public static int getNumRank(int[] nums, int num) {
        int rank = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > num)
                rank++;
        }
        return rank;
    }

    /**
     * 504. 七进制数
     *
     * @param num
     * @return
     */
    public static String convertToBase7(int num) {
        String result = "";
        if (Math.abs(num) < 7) {
            return String.valueOf(num);
        }
        int temp = Math.abs(num);
        while (temp >= 7) {
            result += temp % 7;
            temp = temp / 7;
        }
        result += temp;
        int c = 0, i = 0;
        result = new StringBuffer(result).reverse().toString();
        for (; i < result.toCharArray().length; i++) {
            if (result.toCharArray()[i] == 0 && c == i) {
                result = result.substring(1);
                c++;
            } else {
                break;
            }
        }
        if (num < 0) {
            result = new StringBuffer(result).insert(0, "-").toString();
        }
        return result;
    }

    /**
     * 475. 供暖器
     *
     * @param houses
     * @param heaters
     * @return
     */
    public static int findRadius(int[] houses, int[] heaters) {
        int result = 0;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        ArrayList<Integer> temp = new ArrayList<>(heaters.length);
        for (int i = 0; i < heaters.length; i++) {
            temp.add(heaters[i]);
        }
        int a = 0, b = 0;
        for (int i = 0; i < houses.length; i++) {
            if (houses[i] > heaters[heaters.length - 1]) {
                result = result > houses[houses.length - 1] - heaters[heaters.length - 1] ? result : houses[houses.length - 1] - heaters[heaters.length - 1];
                break;
            }
            while (temp.size() > 0) {
                if (temp.get(0) < houses[i]) {
                    a = temp.get(0);
                    temp.remove(0);
                } else {
                    if (temp.size() > 0) {
                        b = temp.get(0);
                        if (a > 0) {
                            int resNum = ((houses[i] - a) > (b - houses[i]) ? (b - houses[i]) : (houses[i] - a));
                            result = result > resNum ? result : resNum;
                        } else {
                            result = result > b - houses[i] ? result : b - houses[i];
                        }
                    }
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 476. 数字的补数
     *
     * @param num
     * @return
     */
    public static int findComplement(int num) {
        if (num == 0 || num == 2) return 1;
        if (num == 1) return 0;
        int result = 0;
        ArrayList<Integer> res = new ArrayList<Integer>();
        while (num >= 2) {
            res.add(num % 2);
            num = num / 2;
        }
        if (num > 0) {
            res.add(1);
        }
        Collections.reverse(res);
        for (int i = 0; i < res.size(); i++) {
            result += (res.get(i) > 0 ? 0 : 1) * (Math.pow(2, res.size() - 1 - i));
        }
        return result;
    }

    /**
     * 482. 密钥格式化
     *
     * @param S
     * @param K
     * @return
     */
    public static String licenseKeyFormatting(String S, int K) {
        String result = "";
        String res = S.toUpperCase().replaceAll("-", "");
        if (res.length() == 0) return result;
        int temp = res.length() % K;
        if (temp > 0) {
            result = res.substring(0, temp);
            res = res.substring(temp);
        }
        for (int i = 0; i < res.length(); i += K) {
            result += "-";
            result += res.substring(i, i + K);
        }
        if (result.toCharArray()[0] == '-') {
            result = result.substring(1, result.length());
        }
        return result;
    }

    /**
     * 485. 最大连续1的个数
     *
     * @param nums
     * @return
     */
    public static int findMaxConsecutiveOnes(int[] nums) {
        int result = 0, maxCount = 0;
        if (nums.length == 0) return result;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                maxCount++;
            } else {
                result = result > maxCount ? result : maxCount;
                maxCount = 0;
            }
        }
        result = result > maxCount ? result : maxCount;
        return result;
    }

    /**
     * 492. 构造矩形
     *
     * @param area
     * @return
     */
    public static int[] constructRectangle(int area) {
        int[] result = new int[2];
        int temp = 1, l = 1, w = 1;
        for (int i = 1; i <= area; i++) {
            if (temp < i) break;
            if (area % i == 0) {
                temp = area / i;
                if (i <= temp) {
                    l = temp;
                    w = i;
                }
            }
        }
        result[0] = l;
        result[1] = w;
        return result;
    }

    /**
     * 496. 下一个更大元素 I
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int temp = -1;
            int next = getNextSubscript(nums1[i], nums2);
            for (int j = next; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]) {
                    temp = nums2[j];
                    break;
                }
            }
            result[i] = temp;
        }
        return result;
    }

    public static int getNextSubscript(int num, int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                result = i + 1;
                return result;
            }
        }
        return result;
    }

    /**
     * 500. 键盘行
     *
     * @param words
     * @return
     */
    public static String[] findWords(String[] words) {
        ArrayList<String> result = new ArrayList<>();
        ArrayList<String> test = new ArrayList<>();
        test.add("qwertyuiop");
        test.add("asdfghjkl");
        test.add("zxcvbnm");
        for (int i = 0; i < words.length; i++) {
            if (testWord(words[i], test)) {
                result.add(words[i]);
            }
        }
        return (String[]) result.toArray(new String[0]);
    }

    public static boolean testWord(String word, ArrayList<String> test) {
        boolean flag = true;
        char[] temp = word.toLowerCase().toCharArray();
        int count = 0;
        for (String item : test) {
            if (!item.contains(String.valueOf(temp[0]))) {
                count++;
                continue;
            }
            for (int i = 1; i < temp.length; i++) {
                if (!item.contains(String.valueOf(temp[i]))) {
                    return false;
                }
            }
            return true;
        }
        if (count == 3) flag = false;
        return flag;
    }
}
